Satellite-based navigation systems (also referred to as for use in a radio navigation satellite systems) are becoming increasingly important in a wide range of applications, including handheld devices for position determination, in-car navigation support, and so on. The main satellite navigation system in service at present is the global positioning system (GPS) operated by the United States Department of Defense. A European counterpart satellite navigation system, named Galileo, is planned for launch and service availability later this decade. Numerous other satellite navigation systems like GLONASS (Russia), Compass (China), IRNSS (India) and QZSS (Japan) are currently under modernization or under deployment.
A satellite navigation system comprises a constellation of satellites, each of which broadcasts one or more signals. The satellite emitted signals are received at earth at very low power levels, so that it is difficult to receive them in a deep indoor environment. Investigations are ongoing to make use of pseudolites to extend the service coverage of navigation signals also to deep indoor environments. In order to allow the reception of these pseudolite signals by satellite navigation receivers, the signal structure of the pseudolites may be very similar or identical to the navigation signal emitted by satellites.
The basic components of a navigation signal as emitted by a satellite or a pseudolite are a spreading code (also referred to as a positioning, synchronisation or ranging code) which is combined with the spreading symbol setting the modulation waveform and the navigation data. The resulting combination is then modulated onto a carrier at a set frequency for transmission to earth. Each emitter generally transmits at multiple frequencies, which can help to compensate for ionospheric effects, to improve accuracy and to broadcast more data.
In some cases, multiple signal channels may be modulated onto a single carrier via some appropriate multiplexing scheme. For example, it is planned for Galileo signals to comprise a data channel combined with a pilot channel. The pilot channel contains only a spreading code, but no navigation data, while the data channel contains both the spreading code and the navigation data.
The spreading code component of a satellite signal typically comprises a predetermined sequence of bits (referred to as ‘chips’) and is used to perform two main tasks. Firstly, the spreading code provides a synchronisation and access mechanism to allow a receiver to lock onto a satellite signal. Thus each satellite (and typically each signal broadcast from that satellite) has its own spreading code. When a receiver is first switched on, the receiver frequently does not know which satellite signals can be received, since certain satellites in the constellation will be below the horizon for that particular location at that particular time. The receiver uses the spreading codes to lock onto a signal from a first satellite. Accordingly, a spreading code allows a receiver to distinguish and separate between simultaneously transmitting devices in a situation where all of the transmitting devices are applying the same modulation scheme (but with different spreading codes applied) and transmit at the same carrier frequency. Once a receiver has locked onto the signal from a first satellite, the navigation data in the signal can be accessed. This then provides almanac data for the other satellites in the constellation, and allows the remaining satellites that are visible to the receiver to be acquired relatively quickly.
Many receivers employ a two-phase acquisition process. In the first phase, the receiver performs a simultaneous correlation of the incoming signal against the set of satellite spreading codes. In particular, the receiver searches for a spreading code from any satellite, allowing for any possible timing offset between the satellite and the receiver, and for any possible Doppler shift between the satellite and the receiver (which is dependent on the motion of the satellite in space relative to the user). If a correlation value is found to exceed a predetermined threshold, then a second phase involving a more detailed analysis is performed for the relevant combination of satellite spreading code, timing offset and Doppler shift. This second-phase analysis verifies and confirms or if necessary rejects the initial coarse acquisition. In some cases, a receiver may store or access, e.g. over the Internet, the almanac data about those satellites that are currently visible to the receiver (rather than first having to acquire one satellite signal in order to obtain this information). This is sometimes referred to as assisted-GNSS, and can significantly reduce the time taken to obtain a position determination.
The second main task of a spreading code is to provide a distance estimate from the satellite to the receiver, based on the time that it has taken the signal to travel from the satellite to the receiver. The position of the receiver is then determined in three-dimensional space by using a process of trilateration, given the known positions of the satellites (as specified in the navigation data received from the satellites). In theory, trilateration can be performed with signal information from a minimum of three satellites, assuming that the timing offset between the receiver clock and satellite clocks is known. In practice, this timing offset is generally unknown, except for specialised receivers, so that signal information is obtained from at least one additional satellite to compensate for the unknown time offset at the receiver. If signals from further satellites are available, a statistical position determination can be performed using any appropriate algorithm such as least squares. This can also provide some indication of the error associated with an estimated position.
One important parameter for a spreading code is the chip rate at which the spreading code is transmitted, since this in turn controls the accuracy with which the positional determination can be made. Another important parameter for a spreading code is its total length, in other words the number of chips in the spreading code before it repeats. Spreading codes of infinite length are not practical for a number of reasons, including problems at generation and also at acquisition level. However the finite length of a spreading code can lead to ambiguity in the position determination. A longer length for the spreading code reduces such ambiguity, and also provides better separation of signals from different sources and increases robustness against interference. On the other hand, having a longer repetition length for the spreading code may delay initial acquisition of the signal, as well as requiring more processing capability within the receiver.
The length of the spreading code also impacts the data rate that can be used for the navigation data, since traditionally the navigation data is modulated onto the spreading code sequence applying Binary Phase Shift Keying (BPSK) modulation, i.e. only one bit of navigation data is modulated onto one complete spreading code sequence. In such circumstances, the length of the spreading code reflects the spreading code's chip rate and the data rate for the navigation data (or other data being transmitted on the channel). Alternatively more efficient data modulation schemes like Cyclic Code Shift Keying (CCSK) are currently under investigation for satellite navigation systems. Generally, the longer the repetition length for the spreading code, the lower the bit rate for the navigation data will be.
One known strategy to construct long codes based on shorter length codes is to use a hierarchical or tiered spreading code based on primary and secondary codes. If we assume that a primary code has N1 chips and a secondary code has N2 chips, then the first N1 chips of the overall spreading code correspond to the primary sequence exclusive-ORed with the first chip of the secondary code, the next N1 chips of the spreading code comprise a repeat of the N1 chips of the primary code, this time exclusive-ORed with the second chip of the secondary code, and so on. This gives a total repetition length for the code of N1×N2, however the initial acquisition can be based on the primary code only. The tiered code approach is commonly used for the definition of the spreading codes for a pilot channel signal where no data is to be transmitted.
The use of spreading codes in satellite navigation systems is closely related to code division multiple access (CDMA) communications, which are widely used in terrestrial settings. However, there are some differences between these two contexts. For example, in CDMA, the spreading code is not used for making a position determination, and the selection of spreading codes is therefore not impacted by factors relating to position determination. Conversely, in CDMA, there are normally multiple receivers per transmitter, and each receiver uses a different spreading code for communicating with the transmitter. Accordingly, an important factor for CDMA is supporting a large number of codes that can operate in parallel. In contrast, this factor is less important for satellite navigation, since the total number of codes to be used in a given code set is usually based on the number of satellite transmitters and the number of channels (data/pilot). In a typical case, a number of approximately 70 PRN codes can serve one GNSS constellation, assuming that data and pilot channels are to be provided by the specific signal. Allowance must also be made for an extension of the GNSS by local elements (e.g. pseudolites). For example, for each pseudolite, at least one specific PRN code is required to provide the data channel. If a pilot channel is to be provided for the pseudolite as well, two PRN codes are to be transmitted by the local element. In most cases, this represents only a very small subset of the total overall code space (which is given by 2N−1, where N is the number of bits or chips in a code).
Known spreading codes, as used in both satellite navigation and CDMA systems, are based on pseudo-random noise (PRN) sequences. In order to alleviate the separation of the various channels transmitted by the various transmitters of a satellite navigation system, which show up at the receivers with identical modulation waveforms, it is very important for the cross-channel interference to be as low as possible.
A standard measure of cross-channel interference is given by the cross-correlation function, which provides a measure of the similarity between different PRN sequences. Accordingly, an important figure of merit to evaluate a set of PRN sequences for use as spreading codes is given by the cross-correlation function between pairs of spreading codes. The cross-correlation function θu,v(l) for two PRN sequences u and v, both having a length N, at a time offset of l chips between the two code sequences, is defined by:
                                          θ                          u              ,              v                                ⁡                      (            l            )                          =                              ∑                          n              =              0                                      N              -              1                                ⁢                                          ⁢                                    u              n                        ⁢                                          v                                  n                  +                  l                                            .                                                          (        1        )            where the n-th PRN chip of the sequence u is referred to as un and the n+l-th chip of the sequence v is denoted as vn+l. Each PRN code is periodic (cyclic) in N, so that the N values for sequence v starting at offset l are as follows:(vl, vl+1, . . . , vN−1, v0, v1, . . . , vl−1)  (2)
The position determination in satellite navigation systems is derived from an estimate of the time of arrival (TOA) of the signals, which is determined using the auto-correlation function, θu(l), which for a sequence u at a phase shift of l chips is defined by:
                                          θ            u                    ⁡                      (            l            )                          =                              ∑                          n              =              0                                      N              -              1                                ⁢                                          ⁢                                    u              n                        ⁢                                          u                                  n                  +                  l                                            .                                                          (        3        )            The auto-correlation function in effect measures the similarity (or difference) between any PRN sequence and a time shifted version of the same sequence.
In an ideal system, the cross-correlation values between each pair of spreading codes is zero (for all possible offsets). Likewise, the auto-correlation value for each spreading code is zero for all offsets (time shifts) apart from no time delay, i.e. a phase shift of l=0, for which it is clear that θu(l)=N. However, such ideal behaviour can only be achieved for PRN codes of infinite length. Since infinite PRN codes are not applicable to real-world systems, finite PRN codes have to be identified that resemble this ideal behaviour as closely as possible. A further important practical criterion for a spreading code is to have equal (or nearly equal) numbers of ones and zeros—this is referred to as balancing.
One complication is that the polarity of a spreading code may change at the end of the spreading code—this is how the navigation data can be encoded. This is illustrated schematically below (compare with the sequence of (2) above):(vl, vl+1, . . . , vN−1, −v0, −v1, . . . , −vl−1)  (4)An auto- or cross-correlation function determined in the context of a change in polarity is referred to as an odd auto- or cross-correlation function. An auto- or cross-correlation function determined in the absence of any change in polarity is referred to as an even auto- or cross-correlation function (and matches the formal definition of equation (3) above).
There are two broad classes of known PRN sequences. In a first class, the PRN sequences are generated according to a mathematical algorithm (algebraic formula) in closed form, such that there is some predetermined mathematical relationship between all the spreading codes in the code set. The correlation properties of such a code set follow from the algebraic formula used to generate the code set. Well known PRN sequences that belong to this first class include                Gold codes,        Kasami codes,        Weil codes,        Bent codes        Gong codes,        Paterson codes.These codes can be shown to offer almost ideal auto- and cross-correlation properties. However, such codes face the restriction that they can be just constructed for specific (preset) code lengths. For example, Gold codes as well as Kasami codes, which are usually implemented by linear feedback shift registers (LFSR), can be set up for any length specified by N=2n−1, for integer values n that satisfy mod(n, 4)≠0. In contrast, Weil codes can be constructed for any prime code length. Accordingly, the number of potential code lengths using Weil code sequences significantly exceeds the number of potential code lengths to choose from when using Gold codes or Kasami codes. For example, for 0<N<50000, there exist 5133 prime numbers, whereas the LFSR-based sequences can be set up only for 15 different sequence lengths.        
The GPS satellite navigation system utilizes for its L1 C/A signal spreading codes that are Gold codes, implemented using linear feedback shift registers (LFSRs), in which selected outputs from an N-stage shift register are tapped and fed back to the input. The feedback connections within the LFSR can be represented as a binary polynomial in modulo-2 arithmetic of order n, so that the operation of an LFSR is fully specified by its polynomial and the initial setting of the LFSR. The repetition length of the code is 2n−1, so that a relatively compact LFSR can generate an output with a long repetition length.
In general, the code length is determined by the ratio of the chip rate of the spreading code and the bit rate of the navigation data. If the code length is restricted to an available Gold code (or some other algorithmic form of code), then this implies a constraint on the chip rate and the bit rate, which might in turn impact other considerations, such as acquisition time and positioning accuracy. In consequence, working with LFSR-based PRN codes, it is often not possible to align as desired all three defining elements, i.e. LFSR-based PRN code length, symbol rate and chip rate of the signal, and so the PRN code length often has to be adapted correspondingly. One known option to address such an issue is either to truncate a code or to extend it by adding a number of chips to the output code coming from the LFSR. However, any deviation from the preset code length for such a code generally results in a significant degradation of code performance, especially in terms of increased cross-correlation and out-of-phase autocorrelation. This is illustrated by the example of FIG. 1, which compares the cross-correlation performance of 1023-bit Gold codes (the GPS C/A codes) with a version of this code having just a single bit truncated. In particular, the X-axis of FIG. 1 represents cross-correlation performance, while the Y-axis represents the proportion of total correlations (out of all the different pairings and offsets for the code set) that have the corresponding cross-correlation performance It can be seen that for the GPS C/A codes (green), there is a high peak close to zero (nominally ideal performance) and two subsidiary peaks either side. However, for the truncated GPS C/A codes (blue), the central peak has been significantly reduced, to produce a broader spread of cross-correlation values. Note that the maximum cross-correlation values are larger (i.e. further from the central peak) than the subsidiary peaks from the actual (non-truncated) GPS C/A codes. This can lead to increased interference between channels, and hence degrade signal acquisition.
The second class of known PRN sequences are not based on closed algebraic formulae, but rather are generated using numerical methods. For example, random codes can be constructed for any desired code length, and they can be optimized for any figure of merit (FOM), based generally on cross-correlation and auto-correlation properties, as described, for example, in US 2008/0246655. Another approach in the second class is to use chaotic algorithms to set up PRN sequences that show properties as close to random sequences as possible.
PRN sequences of this second class typically require a higher complexity for the transmitter and receiver, since every single bit of the sequence needs to be stored in memory and then read out in real time (hence this class of sequence is sometimes referred to as a memory code). For example, the set of memory codes for a receiver might be stored within some form of ROM such as flash memory. These codes can then be loaded into the receiver chipset at boot time for use during detection of the spreading codes in the incoming satellite signals. If the complete memory codes are loaded into the receiver chipset itself, this may represent a very significant overhead in terms of storage locations on the receiver chipset. Alternatively, the codes might be loaded into a RAM (external to the receiver chipset), where they would represent only a comparatively small addition to the overall program and/or data storage requirements for general receiver operations. However, in this case a dedicated high-speed interface to feed the codes in real-time from the RAM onto the receiver chipset is likely to be required, as well as some additional internal buffering within the receiver chipset itself.
Furthermore, although a high level of auto- and cross-correlation performance can be achieved for the second category of PRN sequences, PRN sequences that are generated based on known analytical formulae usually significantly outperform random codes of identical length in terms of their auto- and cross-correlation properties.